蟻本 2-6 Carmichael Numbers

code: python

import sys

n = int(input())

# 素数判定O(√n)

def is_prime(n):

i = 2

while i * i <= n:

if n % i == 0:

return False

i += 1

return n != 1 # 1の場合は例外

if is_prime(n):

print('No')

sys.exit() # nが素数であれば、'No'を出力してプログラムを終了する

for x in range(2, n):

if pow(x, n, n) != x:

print('No')

sys.exit() # x^n≡x(mod n) が成り立たないようなxが存在すれば、'No'を出力してプログラムを終了する

print('Yes')